package me.mingshan.leetcode;

import java.util.Arrays;

/**
 * https://leetcode.cn/problems/squares-of-a-sorted-array/description/
 * <p>
 * 给你一个按 非递减顺序 排序的整数数组 nums，返回 每个数字的平方 组成的新数组，要求也按 非递减顺序 排序。
 * <p>
 * <p>
 * <p>
 * 示例 1：
 * <p>
 * 输入：nums = [-4,-1,0,3,10]
 * 输出：[0,1,9,16,100]
 * 解释：平方后，数组变为 [16,1,0,9,100]
 * 排序后，数组变为 [0,1,9,16,100]
 * 示例 2：
 * <p>
 * 输入：nums = [-7,-3,2,3,11]
 * 输出：[4,9,9,49,121]
 *
 * @author hanjuntao
 * @date 2025/6/17 0017
 */
public class L_977_squares_of_a_sorted_array {

    public static void main(String[] args) {
        int[] nums = {1};
        int[] result = sortedSquares2(nums);
        for (int i = 0; i < result.length; i++) {
            System.out.print(result[i] + " ");
        }


        // -4 0 1 3 10
        //
    }

    /**
     * 暴力解法
     * 时间复杂度：O(nlogn)
     *
     * @param nums
     * @return
     */
    private static int[] sortedSquares(int[] nums) {
        for (int i = 0; i < nums.length; i++) {
            nums[i] = nums[i] * nums[i];
        }

        Arrays.sort(nums);
        return nums;
    }

    /**
     * 使用O(N)时间解决
     *
     * 1. 找到两个指针，一个指向第一个大于0的索引前一个，一个指向第一个大于0的索引
     * 2. 循环，谁小谁移动，移动的数要放入结果数组
     * 3. 剩余的还没有处理完成的，直接放到结果数组
     *
     * @param nums
     * @return
     */
    private static int[] sortedSquares2(int[] nums) {
        int gtZeroIndex = -1;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] >= 0) {
                gtZeroIndex = i;
                break;
            }
        }

        int left;
        if (gtZeroIndex == -1) {
            left = nums.length - 1;
        } else {
            left = gtZeroIndex - 1;
        }
        int right = gtZeroIndex;

        int[] result = new int[nums.length];
        int rIndex = 0;

        while (left >= 0 && right >= 0 && right < nums.length) {
            // 谁小谁移动，移动的数要放入结果数组
            if (Math.abs(nums[left]) < Math.abs(nums[right])) {
                result[rIndex] = nums[left] * nums[left];
                left--;
            } else {
                result[rIndex] = nums[right] * nums[right];
                right++;
            }
            rIndex++;
        }

        // 剩余的还没有处理完成的，直接放到结果数组
        while (left >= 0) {
            result[rIndex] = nums[left] * nums[left];
            left--;
            rIndex++;
        }
        while (right >= 0 && right < nums.length) {
            result[rIndex] = nums[right] * nums[right];
            right++;
            rIndex++;
        }

        return result;
    }

}
